Năm 1998, Antonio "Toni" Cipriani (Danny Mastrogiorgio), đã bị buộc phải sống ở nước ngoài sau khi giết một người đàn ông theo lệnh của Salvatore Leone (Frank Vincent), quyết định quay lại Liberty City. Khi đến nơi, Toni được Salvatore và một thành viên của gia đình Leone chào đón, Vincenzo "Lucky Vinnie" Cilli (Joe Lo Truglio), người đã nổi lên trong sự vắng mặt của Toni. Vincenzo được Salvatore hướng dẫn thiết lập Toni với một căn hộ và công việc tại Thành phố Liberty. Không lâu sau, Toni từ bỏ khi nhận ra rằng Vincenzo đã thiết lập một công việc được thiết kế để đảm bảo Toni sẽ bị cảnh sát bắt. Toni sau đó bắt đầu làm việc với một cựu thành viên của gia đình tội phạm Sindacco hiện đang trung thành với Leone, J.D. O'Toole (Greg Wilson), nhưng điều này chỉ tồn tại trong một thời gian ngắn khi một thành viên khác trong gia đình tội phạm Leone được lệnh giết O'Toole vào cùng ngày anh ta có ý định trở thành một người đàn ông được tạo ra trong gia đình.

Một thời gian sau, Toni nhận được một cuộc gọi từ Vincenzo, trong đó anh ta khẳng định rằng anh ta đang xin lỗi về tình huống liên quan đến công việc trước đây của Toni với anh ta và yêu cầu Toni gặp mặt. Tuy nhiên, điều này hóa ra là một cái bẫy được đặt ra bởi Vincenzo để anh ta có được vị trí của Toni trong gia đình Leone. Toni sau đó bị tấn công bởi những kẻ tay sai trung thành với Vincenzo nhưng nhanh chóng khuất phục chúng và giết chết Vincenzo trong quá trình này. Sau cái chết của Vincenzo, Toni tiếp tục làm việc cho Salvatore Leone.

Toni đoàn tụ với mẹ mình chỉ để được đáp ứng bởi sự không tán thành địa vị của ông trong hàng ngũ Leone. Cô ra lệnh đánh vào Toni nhưng anh ta đã giết được những kẻ tấn công thay vào đó, để lại công việc còn dang dở giữa anh và mẹ anh ta. Mối quan hệ của Toni với Salvatore và vợ, Maria, phát triển khi anh tiếp tục làm việc cho họ, cuối cùng dẫn Salvatore đặt niềm tin vào Toni và đặt anh ta vào một căn hộ lớn hơn để đổi lấy Toni đưa họ đến một khu vực hẻo lánh của Thành phố Liberty và tránh xa các cuộc tấn công gia tăng của gia đình Leone bởi các băng đảng khác nhau. Đặc biệt, một cuộc chiến được dàn xếp giữa ba gia đình Mafia hàng đầu là Leones, Sindaccos và Forellis.

Toni tiếp tục làm việc cho gia đình Leone trong nỗ lực thể hiện lòng trung thành của mình và cuối cùng trở thành một người đàn ông được tạo ra. Mẹ của Toni nhận được tin tức và rất phấn khởi khi biết được tình trạng của con trai mình cuối cùng đã tăng lên những gì cô hy vọng và cuối cùng đã hủy bỏ cú đánh mà cô đã đặt hàng trước Toni. Tuy nhiên, lễ kỷ niệm bị cắt ngắn, khi cảnh sát thành phố Liberty đến và bắt giữ Salvatore vì nghi ngờ rằng anh ta là một thủ lĩnh băng đảng chỉ được biết đến với cái tên "Ông lớn". Toni vẫn trung thành với Salvatore và đóng vai trò là luật sư của mình, trong khi tiếp tục chấp nhận công việc từ anh ta dẫn đến việc Toni tấn công các đối thủ của Salvatore, đỉnh điểm là Toni giết chết người đứng đầu gia đình Sindacco, Paulie Sindacco, người là lý do chính cho vụ bắt giữ Salvatore và đã khiến thị trưởng mới bắt giữ Salvatore.

Toni sớm trở thành một nhà lãnh đạo đáng kính trong gia đình Leone. Salvatore cuối cùng được đưa ra xét xử, một sự kiện mà các đối thủ của anh ta dự định sử dụng như một cơ hội để loại bỏ anh ta. Toni nhận ra điều này và can thiệp, giữ Leone an toàn. Sau khi Salvatore được tại ngoại, anh ta kết luận rằng Massimo Torini đứng đằng sau những rắc rối của anh ta và nhận ra rằng để ngăn chặn thị trưởng được bầu gần đây, Miles O'Donovan, từ bỏ các cáo buộc chống lại Leone rằng Torini đã bắt giữ con tin thị trưởng.

Cả Salvatore và Toni đều đến hòn đảo nơi Torini đang giữ thị trưởng và xảy ra một cuộc chiến, dẫn đến việc hai Torini giết chết và sử dụng thời gian với thị trưởng để xác định rằng O'Donovan hiện đang mắc nợ gia đình Leone. Khi trò chơi kết thúc, Salvatore yêu cầu O'Donovan cấp quyền bảo vệ cho gia đình Leone trong khi Toni cố gắng hủy hợp đồng với thị trưởng để đảm bảo nó được cấp. Sau đó, tiết lộ rằng Torini là underboss của chú Salvatore, người đã cố gắng làm suy yếu quyền kiểm soát thành phố của cháu trai ông.